# Exercices sur la complexité — Propositions de solutions

## Exercice A - Complexité diverses

### Fonctions surface1 et surface2

Pour `surface1`: instruction à dénombrer (dans la boucle) : `surface += longueur`,
cette instruction est exécutée `largeur` fois.

Pour `surface2`: instruction à dénombrer (dans la boucle) : `surface = longueur * largeur`,
cette instruction est exécutée une seule fois.

Les deux fonctions fournissent le même résultat. La deuxième est beaucoup
plus efficace : en `O(1)`.

### Fonction somme

Instruction à dénombrer : `total += v` ; soit `n` la taille du tableau (`n = len(tab)`),
cette instructions est exécutée `n` fois. La complexité (en temps de calcul)
est en `O(n)`.


## Exercice B - Nombre mystérieux

Remarquer que l'ordinateur devine toujours en 7 essais au maximum.

L'instruction à dénombrer est `nbessais += 1`. A chaque itération, l'intervalle
`[inf-sup]` est divisé par 2. Cette instruction est donc exécutée `log2(100)` fois.

Ici `100` (l'intervalle de recherche) est la taille des données (`n`). L'algorithme
est en `0(log2(n))`.

Pour une recherche entre `1` et `4000`, `log2(4000) = 12`. Il faut donc modifier
le programme :

- la question : "entre 1 et 4000",
- l'assertion au début : `assert nbmyst >= 1 and nbmyst <= 4000`,
- l'initialisation de sup : `sup = 4000`,
- et l'assertion finale `assert nbessais <= 12`.